package 算法.NiuKe.JZ;


/**
 * @author:谢君臣
 * @Date:2021/3/2115:55
 * @version:1.0
 * @function: 输入一个整数数组，判断该数组是不是某二叉搜索树的后序遍历的结果。如果是则返回true,否则返回false。
 * 假设输入的数组的任意两个数字都互不相同。（ps：我们约定空树不是二叉搜素树）
 */
public class JZ23 {
    public static void main(String[] args) {
        System.out.println(VerifySquenceOfBST(new int[]{}));
    }

    public static boolean VerifySquenceOfBST(int[] sequence) {
        // 后序遍历为 左右中 即 小、 大、 中（中为数组最后一个）
        // 思路： 比较数组中 第一个 大于最后一位的下标划分左右，
        if (sequence.length < 2)
            return true;
        else
            return check(sequence, 0, sequence.length - 1);
    }

    public static boolean check(int[] array, int l, int r) {
        if (l>=r) return true;
        int i = l;
        while (i < r && array[i] < array[r]) i++;
        int j = i;
        while (j<=r && array[j]>array[r])j++;
        return j==r && check(array,l,i-1) && check(array,i,r-1);
    }
    public boolean verifyPostorder(int[] postorder) {
        return recur(postorder, 0, postorder.length - 1);
    }
    boolean recur(int[] postorder, int i, int j) {
        if(i >= j) return true;
        int p = i;
        while(postorder[p] < postorder[j]) p++;
        int m = p;
        while(postorder[p] > postorder[j]) p++;
        return p == j && recur(postorder, i, m - 1) && recur(postorder, m, j - 1);
    }
}
